/**
 * 项目名称: 希尔排序.cpp
 * 项目路径: study/DataStructure/数据结构/排序/插入排序
 * 编辑时间: 2024年08月26日16时39分34秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 希尔排序
 * @param A
 * @param n
 */
void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
    for(d=n/2;d>=1;d/=2)//步长变化
        for(i = d+1;i<=n;++i)
            if(A[i]<A[i-d]){//需将A[i]插入有序增量子表
                A[0]=A[i];//暂存A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];//记录后移,查找插入位置
                A[j+d]=A[0];//插入
            }
}
